#define _CRT_SECURE_NO_WARNINGS 1

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>

using namespace std;

//const int N = 500010;
//int n;
//int a[N];
//
//int main()
//{
//    double s;
//    scanf("%d%lf", &n, &s);
//    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
//
//    sort(a, a + n);
//    long double res = 0, avg = s / n;
//    for (int i = 0; i < n; i++)
//    {
//        long double cur = s / (n - i);
//        if (a[i] < cur) cur = a[i];
//        res += (cur - avg) * (cur - avg);
//        s -= cur;
//    }
//    printf("%.4lf", sqrt(res / n));
//    return 0;
//}

//typedef long long LL;
//
//const int N = 10010, MOD = 1000000009;
//int n, k;
//int a[N];
//
//int main()
//{
//    scanf("%d%d", &n, &k);
//    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
//
//    sort(a, a + n);
//
//    int l = 0, r = n - 1;
//    int sign = 1;
//    int res = 1;
//    if (k % 2)
//    {
//        res = a[r--];
//        if (res < 0)
//        {
//            sign = -1;
//        }
//        k--;
//    }
//    while (k)
//    {
//        LL x = (LL)a[l] * a[l + 1], y = (LL)a[r] * a[r - 1];
//        if (x * sign > y * sign)
//        {
//            res = x % MOD * res % MOD;
//            l += 2;
//        }
//        else
//        {
//            res = y % MOD * res % MOD;
//            r -= 2;
//        }
//        k -= 2;
//    }
//    printf("%d\n", res);
//    return 0;
//}

//const int N = 100010;
//
//int n, m;
//long long a[2 * N];
//
//int main()
//{
//    scanf("%d%d", &n, &m);
//    int s = n + m + 1;
//    for (int i = 0; i < s; i++) scanf("%lld", &a[i]);
//    
//
//    long long res = 0;
//    if (!m)
//    {
//        for (int i = 0; i < s; i++) res += a[i];
//    }
//    else
//    {
//        sort(a, a + s);
//        res = a[s - 1] - a[0];
//        for (int i = 1; i < s - 1; i++) res += abs(a[i]);
//    }
//    printf("%lld\n", res);
//    return 0;
//}

//const int N = 100010;
//int n;
//int a[N];
//
//int gcd(int a, int b)
//{
//    return b ? gcd(b, a % b) : a;
//}
//
//int main()
//{
//    scanf("%d", &n);
//    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
//    sort(a, a + n);
//
//    int d = 0;
//    for (int i = 1; i < n; i++) d = gcd(a[i] - a[0], d);
//    if (!d)
//    {
//        printf("%d", n);
//    }
//    else
//        printf("%d", (a[n - 1] - a[0]) / d + 1);
//    return 0;
//}

//int removeDuplicates(vector<int>& nums) {
//    int fast = 0;
//    int slow = 0;
//    while (fast < nums.size())
//    {
//        if (nums[fast] != nums[slow])
//        {
//            slow++;
//            nums[slow] = nums[fast];
//        }
//        fast++;
//    }
//    return slow + 1;
//}

int findKthLargest(vector<int>& nums, int k) {
    auto it = nums.begin();
    priority_queue<int, vector<int>, greater<int>> pq = { it,it + k };
    for (int i = k; i < nums.size(); i++)
    {
        int t = pq.top();
        if(nums[i]>t)
        {
            pq.pop();
            pq.push(nums[i]);
        }
    }
    return pq.top();
}

int main()
{
    vector<int> v = { 3,2,3,1,2,4,5,5,6 };
    findKthLargest(v, 4);
    return 0;
}